package com.example.wangzh.mytest;

import android.util.Log;

import com.example.wangzh.mytest.base.BaseActivity;
import com.example.wangzh.mytest.databinding.ActivityReingoldtifoldTestBinding;
import com.example.wangzh.mytest.part.reingold_tifold.Extreme;
import com.example.wangzh.mytest.part.reingold_tifold.TreeNode;

public class ReingoldTifoldTestActivity extends BaseActivity<ActivityReingoldtifoldTestBinding> {
    TreeNode root;

    @Override
    protected void initView() {
        // 创建二叉树，使用整数坐标
        root = new TreeNode("A", 1, 1);
        mBinding.binaryTreeView.setTree(root);
        prepareData();
    }

    private void prepareData() {
        {
            root = new TreeNode("A", 0, 0);
            TreeNode b = new TreeNode("B", 0, 0);
            TreeNode c = new TreeNode("C", 0, 0);
            TreeNode d = new TreeNode("D", 0, 0);
            TreeNode e = new TreeNode("E", 0, 0);
            TreeNode f = new TreeNode("F", 0, 0);
            TreeNode g = new TreeNode("G", 0, 0);
            TreeNode h = new TreeNode("H", 0, 0);
            TreeNode i = new TreeNode("I", 0, 0);
            TreeNode j = new TreeNode("J", 0, 0);
            root.left = b;
            root.right = c;
            b.left = d;
            b.right = e;
            d.left = h;
            d.right = i;
            c.left = f;
            c.right = g;
            f.left = j;
        }

        {
//            root = BinaryTreeUtils.generateRandomTree();
//            BinaryTreeUtils.printTree(root, 0);
        }

        Extreme l = new Extreme(), r = new Extreme();
        setup(root, 0, l, r);
        petrify(root, 0);
        mBinding.binaryTreeView.setTree(root);
    }

    private static final int MINSEP = 1; // 最小间距

    public void setup(TreeNode t, int level, Extreme rmost, Extreme lmost) {
        if (t == null) {
            lmost = new Extreme(null, -1, 0);
            rmost = new Extreme(null, -1, 0);
            return;
        }

        if (t.value.equals("B")) {
            Log.d("Debug", "Level value: " + level);
        }

        t.y = level; // 设置节点的 y 坐标
        TreeNode l = t.left; // 左子节点
        TreeNode r = t.right; // 右子节点
        //极端节点是指子树最底层的最左节点和最右节点
        Extreme lr = new Extreme(),//左子树的右极端节点
                ll = new Extreme(),//左子树的左极端节点
                rr = new Extreme(),//右子树的右极端节点
                rl = new Extreme();//右子树的左极端节点

        setup(l, level + 1, lr, ll); // 递归处理左子树
        setup(r, level + 1, rr, rl); // 递归处理右子树

        if (l == null && r == null) { // 叶子节点
            rmost.addr = t;
            lmost.addr = t;
            rmost.lev = level;
            lmost.lev = level;
            rmost.off = 0;
            lmost.off = 0;
            t.offset = 0;
        } else { // 非叶子节点
            int cursep = MINSEP; // 当前节点的左右子树间距(在当前层放置了子树根节点,还未分离时的间距)
            int rootsep = MINSEP; // 当前节点的左右子树最终应达到的间距(层层分离时,每层都会累加该值)
            int loffsum = 0; // L树的右端(到最下一层时即右极端节点)相对于T的偏移量(正为在右端,负为在左端)
            int roffsum = 0; // R树的左端(到最下一层时即左极端节点)相对于T的偏移量(正为在右端,负为在左端)

            while (l != null && r != null) {//对于左右子树,对于共有的层,逐层分离
                if (cursep < MINSEP) { // 如果当前间距小于最小间距，调整间距
                    rootsep += (MINSEP - cursep);
                    cursep = MINSEP;
                }

                // 更新左子树右端相对于T的偏移量
                if (l.right != null) {
                    loffsum += l.offset;
                    cursep -= l.offset;
                    l = l.right;
                } else {
                    loffsum -= l.offset;
                    cursep += l.offset;
                    l = l.left;
                }

                // 更新右子树左端相对于T的偏移量
                if (r.left != null) {
                    roffsum -= r.offset;
                    cursep -= r.offset;
                    r = r.left;
                } else {
                    roffsum += r.offset;
                    cursep += r.offset;
                    r = r.right;
                }
            }

            // 设置节点的左右子树偏移量
            t.offset = (rootsep + 1) / 2;
            loffsum -= t.offset;
            roffsum += t.offset;

            // 更新极端节点信息
            if (rl.lev > ll.lev || t.left == null) {
                lmost = rl;
                lmost.off += t.offset;
            } else {
                lmost = ll;
                lmost.off -= t.offset;
            }

            if (lr.lev > rr.lev || t.right == null) {
                rmost = lr;
                rmost.off -= t.offset;
            } else {
                rmost = rr;
                rmost.off += t.offset;
            }

            // 处理线程化
            if (l != null && l != t.left) {
                rr.addr.thread = true;
                //如果右边超出了一点,以后t做左树的时候要再向左偏移一点,所以这里给rr设置一个offset
                //如果左树的右极端节点更靠右,就将RR的右树指向左树的当前层子树,否则将RR的左树指向左树的当前层子树
                rr.addr.offset = Math.abs((rr.off + t.offset) - loffsum);
                if (loffsum - t.offset <= rr.off) {
                    rr.addr.left = l;
                } else {
                    rr.addr.right = l;
                }
            } else if (r != null && r != t.right) {
                ll.addr.thread = true;
                ll.addr.offset = Math.abs((ll.off - t.offset) - roffsum);
                if (roffsum + t.offset >= ll.off) {
                    ll.addr.right = r;
                } else {
                    ll.addr.left = r;
                }
            }
        }
    }

    /**
     * 递归遍历树，将相对偏移量转换为绝对坐标
     *
     * @param t    当前节点
     * @param xPos 当前节点的 x 坐标
     */
    public void petrify(TreeNode t, int xPos) {
        if (t != null) {
            t.x = xPos; // 设置当前节点的 x 坐标

            // 如果节点是线程化的，清除线程化标志并设置为叶子节点
            if (t.thread) {
                t.thread = false;
                t.right = null; // 线程化节点必须是叶子节点
                t.left = null;
            }

            // 递归处理左子树和右子树
            petrify(t.left, xPos - t.offset); // 左子树的 x 坐标 = 当前节点的 x 坐标 - 偏移量
            petrify(t.right, xPos + t.offset); // 右子树的 x 坐标 = 当前节点的 x 坐标 + 偏移量
        }
    }
}
